/*
题目链接:https://leetcode.cn/problems/largest-divisible-subset/description/?envType=daily-question&envId=2025-04-06
*/

//题解代码:
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        vector<int> dp(n,1);
        dp[0] = 1;
        int mx = 1,pot=0;
        for(int i=1;i<n;++i){
            for(int j=i-1;j>=0;--j){
                if(nums[i]%nums[j] == 0){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            if(dp[i] > mx){
                mx = dp[i];
                pot = i;
            }
        }
        vector<int> ans;
        while(dp[pot]>0){
            ans.push_back(nums[pot]);
            if(dp[pot]==1) break;
            for(int j=pot-1;j>=0;--j){
                if(nums[pot]%nums[j]==0 && dp[j]==dp[pot]-1){
                    pot = j;
                    break;
                }
            }   
        }
        return ans;
    } 
};
